package com.fang.algorithm.zuo.linked;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description k个节点的组内逆序调整
 * 给定一个单链表的头节点head，和一个正整数
 * 实现k个节点的小组内部逆序，如果最后一组不够k个，则不调整
 * eg：
 * 参数
 * 1->2->3->4->5->6->7->8，k=3
 * 结果
 * 3->2->1->6->5->4->7->8
 * @date 2022/4/23 12:28 上午
 **/
public class Test06_KNodeReverseLinkedList {

    public static class ListNode {
        private int value;
        private ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = new ListNode(5);
        node1.next.next.next.next.next = new ListNode(6);
        node1.next.next.next.next.next.next = new ListNode(7);
        node1.next.next.next.next.next.next.next = new ListNode(8);
        printNode(node1);
//        ListNode reverseNode = reverseKGroup(node1, 3);
        ListNode reverseNode = reverseKGroup1(node1, 3);
        printNode(reverseNode);
    }

    private static ListNode reverseKGroup1(ListNode head, int k) {
        ListNode start = head;
        ListNode end = moveKNode(start, k);
        if (end == null) {
            return head;
        }
        reverseNode(start, end);
        head = end;
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            start = lastEnd.next;
            end = moveKNode(start, k);
            if (end == null) {
                return head;
            }
            reverseNode(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

    private static void reverseNode(ListNode start, ListNode end) {
        end = end.next;
        ListNode pre = null;
        ListNode next;
        ListNode cur = start;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }

    private static ListNode moveKNode(ListNode start, int k) {
        ListNode end = start;
        for (int i = 0; i < k; i++) {
            if (end == null) {
                return end;
            }
            end = end.next;
        }
        return end;
    }



























    private static ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = getKGroupEnd(start, k);
        if (end == null){
            return head;
        }
        head = end;
        reverse(start, end);
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            start = lastEnd.next;
            end = getKGroupEnd(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

    public static void reverse(ListNode start, ListNode end) {
        // end移动至下一个节点位置
        end = end.next;
        ListNode pre = null;
        ListNode next = null;
        ListNode curr = start;
        while (curr != end) {
            // 移动next
            next = curr.next;
            // 给curr下一个节点反转链接
            curr.next = pre;
            // 移动pre
            pre = curr;
            // 移动curr
            curr = next;
        }
        start.next = end;
    }

    public static ListNode getKGroupEnd(ListNode start, int k) {
        if (null == start || k <= 1) {
            return start;
        }
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    private static void printNode(ListNode reverseNode) {
        while (reverseNode != null) {
            System.out.print(reverseNode.value + "->");
            reverseNode = reverseNode.next;
        }
        System.out.println();
    }
}
